/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package chanlib;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author robit
 */
public class Chan_algo {
    public static void BFS() {
        int N = 5;
        int adj[][] = {{0, 1, 0, 0, 0},
            {1, 0, 0, 0, 0},
            {0, 0, 0, 1, 1},
            {0, 0, 1, 0, 0},
            {0, 0, 1, 0, 0}
        };//test
        boolean checked[] = new boolean[N];
        Queue<Integer> bfs = new LinkedList<Integer>();
        StringBuilder rep = new StringBuilder();//test
        for (int v = 0; v < N; v++) {
            if (checked[v]) {
                continue;
            }
            checked[v] = true;
            bfs.add(v);
            while (!bfs.isEmpty()) {
                Integer h = bfs.poll();
                if (h == null) {
                    break;
                }
                rep.append(' ').append(h);//test
                for (int t = 0; t < N; t++) {
                    if (checked[t] || adj[h][t] == 0) {
                        continue;
                    }
                    checked[t] = true;
                    bfs.add(t);
                }
            }
            bfs.clear();

            System.out.println(rep);//test
            rep.delete(0, rep.length());//test
        }
    }

   public static void insertionSort(){
        int N= 5;//test
        int T[]={1,0,3,4,2};//test
        int P[]={75,555,34,8,-1};//test
        for(int j=1;j<N;j++){
            int key=T[j];
            int value=P[j];
            int i=j-1;
            while(i>=0&&T[i]>key){
                T[i+1]=T[i];
                P[i+1]=P[i];
                i--;
            }
            T[i+1]=key;
            P[i+1]=value;
        }
        System.out.println(Arrays.toString(P));//test
    }

   ////////////// Union find /////////////

    public static Integer head[];
    public static Integer deep[];
    public static void initUnion(int size){
        head=new Integer[size];
        deep=new Integer[size];
        Arrays.fill(deep, 0);
        for(int i=0;i<size;i++){
            head[i]=i;
        }
    }
    public static void create(int a){
        head[a]=a;
    }
    public static int findhead(int a){
        int itr=a;
        while(head[itr]!=itr)
            itr=head[itr];
        final int root= itr;
        itr=a;
        while(head[itr]!=root){
            int tmp=head[itr];
            head[itr]=root;
            itr=tmp;
        }
        return root;
    }
        
    public static void unionset(int a, int b)
    {
        int heada = findhead(a);
        int headb=findhead(b);
        if(heada==headb)
            return;
        if(deep[heada]>deep[headb])
            head[headb]=heada;
        else if(deep[headb]>deep[heada])
            head[heada]=headb;
        else
        {
            head[headb]=heada;
            deep[heada]++;
        }
    }
    
    // head will be chosen based on what come first in natural order
    public static void unionSorted(int a, int b){
        int heada=findhead(a), headb=findhead(b);
        if(heada<headb) head[headb]=heada;
        else head[heada]=headb;
    }

}
